#pragma once
#include <cstring>

class Merge {

private:

public:
	int* doMerge(int* array, int left_index, int right_index, int* outputArray) {
		if (right_index - left_index == 0) {
			//outputArray[left_index] = array[left_index];
			//return outputArray + left_index;
			return array + left_index;
		}
		int mid_index = left_index + (right_index - left_index) / 2;
		int* leftArray = doMerge(array, left_index, mid_index, outputArray);
		int* rightArray = doMerge(array, mid_index + 1, right_index, outputArray);

		int left_length = mid_index - left_index + 1, right_length = right_index - mid_index;
		int i = 0, j = 0, k = 0;
		int* temp = new int[left_length + right_length];
		while (i < left_length && j < right_length ) {
			leftArray[i] < rightArray[j] ? temp[k++] = leftArray[i++] : temp[k++] = rightArray[j++];
		};

		while (i < left_length)
		{
			temp[k++] = leftArray[i++];
		}
			
		while (j < right_length)
		{
			temp[k++] = rightArray[j++];
		}

		memcpy(outputArray + left_index, temp, (left_length + right_length) * sizeof(int));

		delete[] temp;

		return outputArray + left_index;
	}
};